//#include <iostream>
//#include <deque>
//
//using namespace std;
//
//const int N = 1e6 + 10;
//
//int n, k;
//int a[N];
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	deque<int> q;
//	for (int i = 1; i <= n; i++)
//	{
//		while (q.size() && a[q.back()] >= a[i])
//		{
//			q.pop_back();
//		}
//
//		q.push_back(i);
//
//		if (q.back() - q.front() + 1 > k)
//		{
//			q.pop_front();
//		}
//
//		if (i >= k)
//			cout << a[q.front()] << " ";
//	}
//
//	cout << endl;
//
//	q.clear();
//	for (int i = 1; i <= n; i++)
//	{
//		while (q.size() && a[q.back()] <= a[i])
//		{
//			q.pop_back();
//		}
//
//		q.push_back(i);
//
//		if (q.back() - q.front() + 1 > k)
//		{
//			q.pop_front();
//		}
//
//		if (i >= k)
//			cout << a[q.front()] << " ";
//	}
//
//	return 0;
//}


//#include <iostream>
//#include <deque>
//
//using namespace std;
//
//const int N = 1e5 + 10;
//
//int n, m;
//int a[N];
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	deque<int> q;
//	for (int i = 1; i <= n; i++)
//	{
//		while (q.size() && a[q.back()] >= a[i])
//		{
//			q.pop_back();
//		}
//
//		q.push_back(i);
//
//		if (q.back() - q.front() + 1 > m)
//		{
//			q.pop_front();
//		}
//
//		if (i >= m)
//		{
//			cout << a[q.front()] << endl;
//		}
//	}
//
//	return 0;
//}


//#include <iostream>
//
//using namespace std;
//
//const int N = 2e5 + 10;
//
//int n, m;
//int f[N];
//int z, x, y;
//
//int find(int x)
//{
//	if (f[x] == x) return x;
//	return f[x] = find(f[x]);
//}
//
//int main()
//{
//	cin >> n >> m;
//	
//	for (int i = 1; i <= n; i++)
//	{
//		f[i] = i;
//	}
//
//	while (m--)
//	{
//		cin >> z >> x >> y;
//		if (z == 2)
//		{
//			int fx = find(x);
//			int fy = find(y);
//			if (fx == fy)
//				cout << 'Y' << endl;
//			else cout << 'N' << endl;
//		}
//		else
//		{
//			int fx = find(x);
//			int fy = find(y);
//			f[fx] = fy;
//		}
//	}
//
//	return 0;
//}

//#include <iostream>
// 
//using namespace std;
//
//const int N = 5e3;
//
//int f[N];
//int n, m, p;
//int m1, m2;
//int p1, p2;
//
//int find(int x)
//{
//	if (f[x] == x) return x;
//	return f[x] = find(f[x]);
//}
//
//void un(int x, int y)
//{
//	int fx = find(x);
//	int fy = find(y);
//	f[fx] = fy;
//}
//
//bool issame(int x, int y)
//{
//	int fx = find(x);
//	int fy = find(y);
//	return fx == fy;
//}
//
//int main()
//{
//	cin >> n >> m >> p;
//	for (int i = 1; i <= n; i++)
//	{
//		f[i] = i;
//	}
//
//	while (m--)
//	{
//		cin >> m1 >> m2;
//		un(m1, m2);
//	}
//
//	while (p--)
//	{
//		cin >> p1 >> p2;
//		if (issame(p1, p2))
//			cout << "Yes" << endl;
//		else
//			cout << "No" << endl;
//	}
//
//	return 0;
//}